1. Field of the Invention
This invention relates to a data processing method, a data recording apparatus and a data transmission apparatus. More particularly, the present invention relates to a data processing method, a data recording apparatus and a data transmission apparatus adapted to encode data by combining interleaving and error-correcting codes in order to efficiently correct burst errors that can take place in a region of a certain size across a plurality of tracks or a plurality of communication channels when recording digital data by means of a magnetic tape recording apparatus or an optical disc recording apparatus and transmitting digital data by means of a multi-input, multi-output (MIMO) transmission system or some other transmission system.
2. Description of the Related Art
When recording digital data on a plurality of recording tracks arranged in parallel (e.g., side by side) on a recording medium by means of a magnetic tape recording apparatus or an optical disc recording apparatus or transmitting digital data by means of a multi-input, multi-output (MIMO) transmission system, an error burst can take place and part of the recorded information or transmitted information can continuously turn out to be an error. Typical causes of error bursts include, for example, dirt on the recording medium and a faulty reproduction head or optical pickup when a magnetic tape recording apparatus or an optical disc recording apparatus is used and large external turbulence noises that temporarily arise on communication channels when a communication apparatus is used. Other major causes of error bursts that may involve recording apparatus or communication apparatus include reproduced or received signals that have stepped out of synchronism.
With one of the popular techniques that are employed to efficiently correct burst errors of signals, input data are coded by combining error-correcting codes and interleaving (shuffling). The size of error burst that can be corrected is determined by the code parameters and the interleaving method that are employed.
For example, RS product codes formed by combining two Reed Solomon (RS) codes are often used as error-correcting codes to be combined with interleaving in magnetic tape recording apparatus and optical disc recording apparatus. An RS code is a code defined on a Galois Field (GF) and expressed by means of parameters (n, k, d), where n represents the code word length, k represents the information word length and d represents the minimum distance between code words. It is characterized in that it can correct up to (d−1) /2 symbol errors in a code word. When information on missing input data is available, it is possible to correct up to d−1 symbols by means of a decoding process, which is referred to as missing correction.
FIG. 1 of the accompanying drawings illustrate the structure of a product code word formed by combining two RS codes of C1 (n1, k1, d1) and C2 (n2, k2, d2). The product code word is obtained typically by coding each of the columns 0, 1, . . . , (k1−1) by means of the C2 code for a total of k1×k2 input data (product code information words) {D0, D1, . . . , Dk1×k2−1}, adding the parities of n2−k2 symbols, subsequently coding the data of each row by means of the C1 code and adding the C1 parities of n1−k1symbols. When decoding the C1 code first for each row of the product code word, the data included in the C1 code word detected by error detection are treated as missing data and then it is possible to execute a process of missing correction by means of the C2 code. For example, if it is not possible to correct a plurality of C1 code words because of the errors that arises, it is possible to correct errors of up to d2−1 C1 code words in the product code word because only the symbols included in the C1 code words that could not be corrected when decoding C2 in each column turn out to be errors.
Patent Document 1 (U.S. Pat. No. 6,539,514) describes a recording method that can be used when recording eight RS product code words on eight tracks of a recording medium, using C1 code words as so many data blocks.
The interleaving technique described in Patent Document 1 will be briefly described below. Assume that product codes are formed by using every 12,636 bytes, starting from the leading byte, out of the input data of 101,088 bytes by using RS codes of C1 (240, 234, 7) and C2 (64, 54, 11) on GF (28). As a result, eight product code words (15,360 bytes) as shown in FIG. 2 are obtained. Then, numbers 0 through 511 are sequentially assigned to all the 512 C1 code words (240 bytes) that constitute the eight product code words. These C1 code words are arranged on eight tracks in a format as illustrated in FIG. 3 by interleaving. Note, however, any two adjacently located recording tracks in FIG. 3 may not necessarily be physically arranged side by side on the recording medium. In other words, other recording tracks may exist between any two adjacent ones of the recording tracks illustrated in FIG. 3. The hatched partitions in FIG. 3 are C1 code words that belong to the first product code word so that it will be appreciated that the C1 code words that belong to a same product code word arranged recurrently in a diagonal direction. With this arrangement, if a burst error arises, involving all given tracks, but the data on the remaining seven tracks can be read correctly, 56 C1 code words of each product code word are read correctly except the eight C1 code words on the track where the burst error arises so that the product code word can be correctly decoded by missing correction at the time of decoding C2 codes.
On the other hand, Latin squares are known as a pattern formed by arranging a total of L numbers from 0 to L−1 in an L×L square (L is a natural number not smaller than 2). In a Latin square, a same number does not appear twice or more than twice in a same row and in a same column.
With the interleaving technique of Patent Document 1, each product code word is made to repeat the leading 8×8 arrangement pattern and the arrangement pattern determine the format of interleaving. An 8×8 Latin square is obtained by taking out the 8×8 region (A in FIG. 4), sorting the C1 code words by means of the product code words to which the C1 code words belong and assigning numbers of 0 through 7 to the eight product code words (B in FIG. 4). Note that, in FIG. 4, the blocks of the C1 code words that belong to the first (0-th) product code word are hatched.
Non-Patent Document 1 (K. Kim and V. K. P. Kumar, “Perfect Latin Squares and Parallel Array Access”, Computer Architecture, 1989, the 16th Annual International Symposium on 28 May-1 June, pp. 372-379, 1989) introduces an arrangement referred to as perfect Latin square as a special type of Latin square.
In a perfect Latin square, a same number does not appear in a same diagonal line in addition to the characteristic of an M2×M2 (M is a natural number not smaller than 2) square that a same number does not appear twice or more than twice on each row and each column and, if the square is divided into M×M regions as shown in FIG. 5, a same number does not appear in each of the regions produced by dividing the Latin square. FIG. 5 shows an example of a perfect 9×9 Latin square (M=3). Non-Patent Document 1 also describes a method of generating a perfect Latin square, using two M×M Latin squares that are orthogonal relative to each other. Thus, the probability of occurrence of errors that concentrate in a code word will be reduced when an error burst arises to spread two dimensionally by using such an arrangement for interleaving the original code words if compared with the interleaving technique described in the above-cited Patent Document 1.